package week02

import "sort"

// 56. 合并区间
// https://leetcode-cn.com/problems/merge-intervals/

func merge(intervals [][]int) [][]int {
	sort.Sort(SliSort(intervals))

	var ans [][]int
	var start = -1
	var far = -1
	for _, interval := range intervals {
		if far >= interval[0] { // 相交，合并
			far = max(interval[1], far)
		} else {    // 新开一段
			if start > -1 && far > -1 {
				ans = append(ans, []int{start, far})
			}
			start = interval[0]
			far = interval[1]
		}
	}
	if start > -1 && far > -1 {
		ans = append(ans, []int{start, far})
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

type SliSort [][]int

func (s SliSort) Len() int { return len(s) }
func (s SliSort) Less(i, j int) bool { return s[i][0] < s[j][0] }
func (s SliSort) Swap(i, j int) { s[i], s[j] = s[j], s[i]}